/*
Gas Station


There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). 
You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.
*/

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <sstream>
#include <unordered_set>
#include "print.h"
using namespace std;

/**
* Definition for binary tree*/


void testForStack()
{
	stack<int> mystack;
	mystack.push(10);
	mystack.push(20);
	mystack.top() -= 5;
	cout << "mystack.top() is now " << mystack.top() << endl;
}

void testForIntToString()
{
	int a = 10;
	stringstream ss;
	ss << a;
	string str = ss.str();
	cout << str << endl;

	string str1 = to_string(a);

}



class Solution1 {
public:
	bool runCircuit(vector<int>& gas, vector<int>& cost,int start)
	{
		int tank = 0;
		int size = gas.size();

		for (int i = 0; i < size; i++)
		{
			tank = gas[(start+i)%size]-cost[(start+i)%size];
			if (tank <0)
			{
				return false;
			}

		}

		return true;

	}
	int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
		if (gas.size()==0||cost.size()==0)
		{
			return -1;
		}
		if (gas.size() != cost.size())
		{
			return -1;
		}

		bool flag = false;
		int start = -1;
		for (int i = 0; i < gas.size(); i++)
		{
			start = i;
			flag = runCircuit(gas,cost,start);
			if (flag)
			{
				return start;
			}
		}

		return start;
	}
};




class Solution {
public:
	
	int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
		int dif = 0;
		int total = 0;
		int start = 0;
		for (int i = 0; i < gas.zie(); i++)
		{
			dif += gas[i] - cost[i];
			total += gas[i] - cost[i];

			if (dif<0)
			{
				start = (i + 1) % gas.size();
				dif = 0;
			}
		}
		if (total<0)
		{
			return -1;
		}
		else
		{
			return start;
		}
	
	}
};



int main(int argc, char* argv[])
{



	string start = "hit";
	string end = "cog";


	//cout << "Input the string" << endl;
	//string str;

	//cin >> str;

	string str = "aab";





	vector<vector<string>> result;



	Solution s;
	result = s.partition(str);
	//stackTree.push(p->left);
	//stackTree.push(p->right);
	//if (s.isPalindrome(str1))
	//	cout << " True" << endl;
	//else
	//	cout << "false" << endl;
	system("pause");
	return 0;
}
//std::unordered_set<std::string> myset =
//{ "hot", "dot", "dog", "lot", "log" };

//std::cout << "myset contains:";
// for (auto it = myset.begin(); it != myset.end(); ++it)
//std::cout << " " << *it;
//;; std::cout << std::endl;

//TreeNode *root = new TreeNode(1);
//TreeNode *left = new TreeNode(2);
//TreeNode *right = new TreeNode(3);

//root->left = left;
//root->right = right;